package randomthoughts.dp;

/**
 * @author tongchen
 * @create 2023-04-15 20:20
 */
public class EqualSumSubset {
    public static void main(String[] args) {

    }

    /**Leetcode 416
     * 五部曲：1.数组 dp[i]:容量为i的情况下的最大价值 i代表容量 2.递推公式：dp[i]=max(dp[i],dp[i-weight[i]]+value[i])
     * 3.初始化：dp[0]=0;4.遍历顺序：一层是物品，二层是背包容量，背包容量是从后往前遍历
     * @param nums
     * @return
     */
    public static boolean isEqualSum(int[]nums,int target){
        //定义数组和
        int sum=0;
        for (int i:nums) {
            sum+=i;
        }
        //创建数组
        int[]dp=new int[sum+1];
        for(int i=0;i< nums.length;++i){
            for(int j=sum;j>=nums[i];--j){
                dp[j]=Math.max(dp[j],dp[j-nums[i]]+nums[i]);
            }
        }
        //最后进行判断
        if(dp[target]==target){
            return true;
        }else{
            return false;
        }
    }
}
